package com.frx.datastruct.chapterthirteen;

/**
 * @author ：frx
 * @date ：Created in 2019/6/25 21:30
 * @description： 红黑树
 * @modified By：
 * @version: ToDO
 */
public class RBTree<K extends Comparable<K>,V> {

    private static final  boolean RED = true;
    private static final  boolean BLACK = false;
    private class Node{

        public K key;
        public V value;
        public Node left,right;
        public boolean color;

        public Node(K key, V value){
            this.key = key;
            this.value = value;
            left = right = null;
            color = RED;
        }

    }
    private Node root;
    private int size;

    public RBTree(){
        root = null;
        size = 0;
    }


    public int getSize(){
        return size;
    }

    public boolean isEmpty(){
        return size == 0;
    }

    /**
     * @description 判断节点的颜色
     * @param node
     * @return
     */
    public boolean isRed(Node node){
        if (node == null){
            return BLACK;
        }
        return node.color;
    }

    public void add(K key, V value){
        // 执行完插入操作之后要保持根节点为黑色
        root.color = BLACK;
    }

    /**
     *       node                             x
     *      /   \        左旋转              /  \
     *     T1    x    ------------>      node  T3
     *          / \                     /   \
     *         T2  T3                  T1   T2
     * */

    private Node leftRotate(Node node){
        Node x = node.right;
        // 左旋转
        node.right = x.left;
        x.left = node;

        x.color = node.color;
        node.color = RED;

        return x;
    }

}
